home *** CD-ROM | disk | FTP | other *** search
/ Aminet 24 / Aminet 24 (1998)(GTI - Schatztruhe)[!][Apr 1998].iso / Aminet / comm / mail / Mutt089src.lha / Mutt-0.89i-AMIGA / src / thread.c < prev   
C/C++ Source or Header  |  1998-01-28  |  14KB  |  573 lines
  1. /*
  2.  * Copyright (C) 1996-8 Michael R. Elkins <me@cs.hmc.edu>
  3.  *
  4.  *     This program is free software; you can redistribute it and/or modify
  5.  *     it under the terms of the GNU General Public License as published by
  6.  *     the Free Software Foundation; either version 2 of the License, or
  7.  *     (at your option) any later version.
  8.  * 
  9.  *     This program is distributed in the hope that it will be useful,
  10.  *     but WITHOUT ANY WARRANTY; without even the implied warranty of
  11.  *     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12.  *     GNU General Public License for more details.
  13.  * 
  14.  *     You should have received a copy of the GNU General Public License
  15.  *     along with this program; if not, write to the Free Software
  16.  *     Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  17.  */ 
  18.  
  19. #include "mutt.h"
  20. #include "sort.h"
  21.  
  22. #include <string.h>
  23. #include <ctype.h>
  24.  
  25. /* This function makes use of the fact that Mutt stores message references in
  26.  * reverse order (i.e., last to first).  This is optiminal since we would like
  27.  * to find the most recent message to which "cur" refers itself.
  28.  */
  29. static HEADER *find_reference (HEADER *cur, CONTEXT *ctx)
  30. {
  31.   LIST *refs = cur->env->references;
  32.   int i, j;
  33.  
  34.   for (; refs; refs = refs->next)
  35.   {
  36.     /* If the mailbox is already mostly sorted (such as when new mail arrives),
  37.      * the reference is likely to be just before the current message, so
  38.      * searching backward from this message first could save some time.
  39.      *
  40.      * Note: cur == ctx->hdrs[ cur->msgno ]
  41.      */
  42.  
  43.     for (j = 0; j <= 1; j++)
  44.     {
  45.       i = cur->msgno;
  46.  
  47.       if ((j == 0) ^ (ctx->revsort == 0))
  48.       {
  49.     while (++i < ctx->msgcount)
  50.     {
  51.       if (ctx->hdrs[i]->env->message_id &&
  52.           !strcmp (refs->data, ctx->hdrs[i]->env->message_id))
  53.         return (ctx->hdrs[i]);
  54.     }
  55.       }
  56.       else
  57.       {
  58.     while (--i >= 0)
  59.     {
  60.       if (ctx->hdrs[i]->env->message_id &&
  61.           !strcmp (refs->data, ctx->hdrs[i]->env->message_id))
  62.         return (ctx->hdrs[i]);
  63.     }
  64.       }
  65.     }
  66.   } 
  67.  
  68.   return NULL;
  69. }
  70.  
  71. static HEADER *find_subject (HEADER *cur, HEADER **tree, int size)
  72. {
  73.   HEADER *last = NULL;
  74.   int i, curno = 0;
  75.  
  76.   if (cur->env->real_subj &&
  77.       ((cur->env->real_subj != cur->env->subject) || (!option (OPTSORTRE))))
  78.   {
  79.     for (i = 0; i < size; i++)
  80.     {
  81.       if (tree[i] == cur)
  82.       {
  83.     /* save the current position so we can replace it if we find a
  84.      * matching subject
  85.      */
  86.     curno = i;
  87.       }
  88.       else if (cur->date_sent >= tree[i]->date_sent &&
  89.            (!last || (last->date_sent <= tree[i]->date_sent)) &&
  90.            tree[i]->env->real_subj &&
  91.            strcmp (cur->env->real_subj, tree[i]->env->real_subj) == 0)
  92.       {
  93.     last = tree[i];
  94.       }
  95.     }
  96.   }
  97.   if (last)
  98.   {
  99.     /* since we found a matching subject, remove this message from the list
  100.      * of toplevel messages and fill the hole with the last message in the
  101.      * list.  this reduces the number of searches the next time around.
  102.      * note that `size' gets decremented in the pseudo_threads() function
  103.      * when this functions returns non-NULL
  104.      */
  105.     tree[curno] = tree[size - 1];
  106.   }
  107.   return last;
  108. }
  109.  
  110. /* Since the graphics characters have a value >255, I have to resort to
  111.  * using escape sequences to pass the information to print_enriched_string().
  112.  *
  113.  *   '\001': lower corner  (ACS_LLCORNER)
  114.  *   '\002': upper corner  (ACS_ULCORNER)
  115.  *   '\003': left tee      (ACS_LTEE)
  116.  *   '\004': horiz. line   (ACS_HLINE)
  117.  *   '\005': vertical line (ACS_VLINE)
  118.  *   '\006': space         ( )
  119.  *   '\007': greater than  (>)
  120.  *   '\010': asterisk      (*)
  121.  *
  122.  * ncurses should automatically use the default ASCII characters instead of
  123.  * graphics chars on terminals which don't support them (see the man page
  124.  * for curs_addch).
  125.  */
  126. static void linearize_tree (HEADER *tree, HEADER **array)
  127. {
  128.   char *pfx = NULL, *mypfx = NULL;
  129.   int depth = 0, max_depth = 0;
  130.   char corner = Sort & SORT_REVERSE ? '\002' : '\001';
  131.  
  132.   /* A NULL tree should never be passed here, but may occur if there is
  133.    * a cycle.
  134.    */
  135.   if (!tree)
  136.     return;
  137.  
  138.   FOREVER
  139.   {
  140.     if (tree->subject_changed || (tree->prev && tree->prev->subject_changed))
  141.       tree->display_subject = 1;
  142.     else 
  143.       tree->display_subject = 0;
  144.  
  145.     if (depth >= max_depth)
  146.       safe_realloc ((void **) &pfx, (max_depth += 32) * 2 * sizeof (char));
  147.  
  148.     if (depth)
  149.     {
  150.       mypfx = pfx + (depth - 1) * 2 * sizeof(char);
  151.  
  152.       sprintf (mypfx, "%c%c\007",
  153.     tree->next ? '\003' : corner,
  154.     tree->fake_thread ? '\010' : '\004');
  155.     }
  156.     else
  157.       pfx[0] = 0;
  158.  
  159.     safe_free ((void **) &tree->tree);
  160.     tree->tree = safe_strdup (pfx);
  161.  
  162.     *array = tree;
  163.     array += Sort & SORT_REVERSE ? -1 : 1;
  164.  
  165.     if (tree->child)
  166.     {
  167.       if (depth)
  168.       {
  169.     mypfx[0] = tree->next ? '\005' : '\006';
  170.     mypfx[1] = '\006';
  171.       }
  172.       tree = tree->child;
  173.       depth++;
  174.     }
  175.     else
  176.     {
  177.       while (!tree->next && tree->parent)
  178.       {
  179.     tree = tree->parent;
  180.     depth--;
  181.       }
  182.       if (!(tree = tree->next))
  183.     break;
  184.     }
  185.   }
  186.  
  187.   safe_free ((void **) &pfx);
  188. }
  189.  
  190. /* inserts `msg' into the list `tree' using an insertion sort.  this function
  191.  * assumes that `tree' is the first element in the list, and not some
  192.  * element in the middle of the list.
  193.  */
  194. static void insert_message (HEADER **tree, HEADER *msg, sort_t *sortFunc)
  195. {
  196.   HEADER *tmp;
  197.  
  198.   /* NOTE: we do NOT clear the `msg->child' link here because when we do
  199.    * the pseudo-threading, we want to preserve any sub-threads.  So we clear
  200.    * the `msg->child' in the main routine where we know it is safe to do.
  201.    */
  202.  
  203.   /* if there are no elements in the list, just add it and return */
  204.   if (!*tree)
  205.   {
  206.     msg->prev = msg->next = NULL;
  207.     *tree = msg;
  208.     return;
  209.   }
  210.  
  211.   /* check to see if this message belongs at the beginning of the list */
  212.   if (!sortFunc || sortFunc ((void *) &msg, (void *) tree) < 0)
  213.   {
  214.     (*tree)->prev = msg;
  215.     msg->next = *tree;
  216.     msg->prev = NULL;
  217.     *tree = msg;
  218.     return;
  219.   }
  220.   
  221.   /* search for the correct spot in the list to insert */
  222.   for (tmp = *tree; tmp->next; tmp = tmp->next)
  223.     if (sortFunc ((void *) &msg, (void *) &tmp->next) < 0)
  224.     {
  225.       msg->prev = tmp;
  226.       msg->next = tmp->next;
  227.       tmp->next->prev = msg;
  228.       tmp->next = msg;
  229.       return;
  230.     }
  231.  
  232.   /* did not insert yet, so add this message to the end of the list */
  233.   tmp->next = msg;
  234.   msg->prev = tmp;
  235.   msg->next = NULL;
  236. }
  237.  
  238. static HEADER *pseudo_threads (HEADER *list, HEADER **array, int size,
  239.                    sort_t *sortFunc)
  240. {
  241.   HEADER *top = list, *cur, *tmp, *curchild, *nextchild;
  242.  
  243.   while (list)
  244.   {
  245.     cur = list;
  246.     list = list->next;
  247.     if ((tmp = find_subject (cur, array, size)) != NULL)
  248.     {
  249.       size--;
  250.       /* detach this message from it's current location */
  251.       if (list)
  252.     list->prev = cur->prev;
  253.       if (cur != top)
  254.     cur->prev->next = cur->next;
  255.       else
  256.     top = cur->next;
  257.  
  258.       cur->subject_changed = 0;
  259.       cur->fake_thread = 1;
  260.       cur->parent = tmp;
  261.       insert_message (&tmp->child, cur, sortFunc);
  262.       
  263.       /* if the message we're attaching has pseudo-children, they
  264.        * need to be attached to its parent, so move them up a level.
  265.        */
  266.       curchild = cur->child;
  267.       while (curchild)
  268.       {
  269.     nextchild = curchild->next;
  270.     if (curchild->fake_thread)
  271.     {
  272.       /* detach this message from its current location */
  273.       if (curchild->next)
  274.         curchild->next->prev = curchild->prev;
  275.       if (curchild->prev)
  276.         curchild->prev->next = curchild->next;
  277.       else
  278.         cur->child = curchild->next;
  279.       curchild->parent = tmp;
  280.       insert_message (&tmp->child, curchild, sortFunc);
  281.     }
  282.     curchild = nextchild;
  283.       }
  284.     }
  285.   }
  286.   return top;
  287. }
  288.  
  289. static HEADER *sort_last (HEADER *top)
  290. {
  291.   HEADER *tree;
  292.   HEADER *tmp;
  293.   HEADER *first;
  294.   HEADER *last;
  295.   HEADER *nextsearch;
  296.   sort_t *usefunc;
  297.   
  298.   usefunc = mutt_get_sort_func (Sort);
  299.   
  300.   tree = top;
  301.   FOREVER
  302.   {
  303.     if (tree->child)
  304.       tree = tree->child;
  305.     else
  306.     {
  307.       while (!tree->next)
  308.       {
  309.     first = last = tree;
  310.     nextsearch = tree->prev;
  311.     first->prev = NULL;
  312.     last->next = NULL;
  313.     while ((tree = nextsearch) != NULL)
  314.     {
  315.           tmp = last;
  316.           nextsearch = nextsearch->prev;
  317.       while (tmp && (*usefunc) ((void *) &tree->last_sor